# -*- coding: utf-8 -*-
# @Author: bao
# @Date:   2017-02-17 11:20:24
# @Last Modified by:   bao
# @Last Modified time: 2017-05-15 19:07:35

from gen_topo import *
from datetime import datetime


class gen_topo_fully(gen_topo):
    """
    Non-blocking circuit switch
    """

    def __init__(self):
        gen_topo.__init__(self)

    def _transform(self, wl_graph, tf_graph, degree, base_len):
        """
        Generate new topology based on multi max_weight_matching (directed bipartite graph)
        node (bp_src, bipartite=0, degree=0)
        node (bp_dst, bipartite=0, degree=0)
        edge (src, dst, 'weight')
        """
        starttime = datetime.now()
        remain_edges = []
        temp_graph = tf_graph.copy()
        while temp_graph.edges():
            match = nx.max_weight_matching(temp_graph, maxcardinality=False)
            # print len(match), match
            for src in match:
                dst = match[src]
                if src <= base_len:
                    # print src, dst, temp_graph[src][dst]['weight']
                    max_degree = max(wl_graph.node[src]['degree'], wl_graph.node[dst]['degree'])
                    if max_degree < degree:
                        traffic_weight = get_weight(temp_graph[src][dst]['weight'])
                        wl_max = degree - max_degree
                        wl_num = min(traffic_weight, wl_max)
                        wl_graph.add_edge(src, dst, weight=wl_num)
                        wl_graph.node[src]['degree'] += wl_num
                        wl_graph.node[dst]['degree'] += wl_num
                    else:
                        remain_edges.append((src, dst))
                    temp_graph.remove_edge(src, dst)
        endtime = datetime.now()
        timediff = endtime - starttime
        print (timediff)
        # print '_transform time ',timediff

    def _matchings(self, graph, pre_matches, max_degree, base_len):
        """
        Minimal Wavelength Adjustment (MWA) based on pre_matches
        Extending the algorithms from paper "WaveCube: A scalable, fault-tolerant, high-performance optical data center architecture"
        """
        starttime = datetime.now()
        wl_graph = graph.copy()
        counter = 1
        max_d = max_degree
        match_results = {}
        remain_pre_matches = {}
        for i in pre_matches:
            max_d_nodes = []  # nodes with degree max_d in graph
            for node in wl_graph.nodes():
                if wl_graph.node[node]['degree'] == max_d:
                    max_d_nodes.append(node)

            inter_nodes = []
            inter_edges = list(set(pre_matches[i]) & set(wl_graph.edges()))  # common edges
            pre_remian_edges = list(set(pre_matches[i]) - set(inter_edges))
            [inter_nodes.extend([src, dst]) for (src, dst) in inter_edges]
            '''
            print '\n', "pre_matches:", i, counter, pre_matches[i]
            print len(set(pre_matches[i])&set(wl_graph.edges())), set(pre_matches[i])&set(wl_graph.edges())
            print "max_degree:", max_d, "max_d_nodes", len(max_d_nodes), max_d_nodes		
            print "inter_edges:", inter_edges
            print "pre_remian_edges:", pre_remian_edges
            '''
            if set(max_d_nodes).issubset(set(inter_nodes)):  # matches i covers all nodes with max_d
                # print "case1: cover all nodes with max_degree d"
                match_results[counter] = pre_matches[i]
                self._update_graph_fully(wl_graph, match_results[counter])
                max_d -= 1
                counter += 1
            else:
                # print "case2: find a matches cover other max_degree d nodes"
                sub_match = []
                sub_graph = wl_graph.copy()
                sub_graph.remove_nodes_from(inter_nodes)
                sub_match_dict = nx.bipartite.maximum_matching(sub_graph)
                [sub_match.append((src, sub_match_dict[src])) for src in sub_match_dict if src <= base_len]

                sub_inter_nodes = []
                [sub_inter_nodes.extend([src, dst]) for (src, dst) in sub_match]

                if (set(max_d_nodes) - set(inter_nodes)).issubset(sub_inter_nodes) \
                        and len(set(sub_match) & set(inter_edges)) == 0:
                    # print "case3: a matches cover other max_degree d nodes !!!"
                    new_match_nodes = []
                    new_match = list(set(sub_match) | set(inter_edges))
                    [new_match_nodes.extend([src, dst]) for (src, dst) in new_match]
                    remain_nodes = list(set(wl_graph.nodes()) - set(new_match_nodes))
                    remain_nodes.sort()
                    # print len(new_match), new_match, remain_nodes
                    if remain_nodes:
                        self._augument_perfect_fully(remain_nodes, new_match, pre_matches[i], base_len)

                    match_results[counter] = new_match
                    self._update_graph_fully(wl_graph, match_results[counter])
                    max_d -= 1
                    counter += 1
                else:
                    remain_pre_matches[i] = pre_matches[i]

        for x in range(counter, max_degree + 1):
            new_match = []
            new_match_nodes = []
            match_dict = nx.bipartite.maximum_matching(wl_graph)
            [new_match.append((src, match_dict[src])) for src in match_dict if src <= base_len]
            [new_match_nodes.extend([src, dst]) for (src, dst) in new_match]
            remain_nodes = list(set(wl_graph.nodes()) - set(new_match_nodes))
            remain_nodes.sort()

            com_len = 0
            index = 0
            for i in remain_pre_matches:
                counter = 0
                for src, dst in remain_pre_matches[i]:
                    if src in remain_nodes and dst in remain_nodes:
                        counter += 1
                counter += len(list(set(remain_pre_matches[i]) & set(new_match)))
                if com_len < counter:
                    index = i
                    com_len = counter

            self._augument_perfect_fully(remain_nodes, new_match, remain_pre_matches[index], base_len)
            del remain_pre_matches[index]
            match_results[x] = new_match
            self._update_graph_fully(wl_graph, match_results[x])
        endtime = datetime.now()
        timediff = endtime - starttime
        print (timediff)
        # print 'matchings time ',timediff
        return match_results

    def _update_graph_fully(self, graph, matches):
        """
        Update the node 'degree' and edge 'weight' based on new mathcing
        """
        for (src, dst) in matches:
            if (src, dst) in graph.edges():
                graph.node[src]['degree'] -= 1
                graph.node[dst]['degree'] -= 1
                if graph.edge[src][dst]['weight'] > 1:
                    graph.edge[src][dst]['weight'] -= 1
                else:
                    graph.remove_edge(src, dst)

    def _augument_perfect_fully(self, remain_nodes, cur_matches, pre_matches, base_len):
        """
        Augment the cur_matches to perfect matches with pre_matches
        Maximizing the overlap between cur_matches and pre_matches
        """
        src_nodes = remain_nodes[:len(remain_nodes) / 2]
        dst_nodes = remain_nodes[len(remain_nodes) / 2:]
        remain_pre_matches = list(set(pre_matches) - set(cur_matches))

        # print src_nodes
        # print dst_nodes
        # print remain_pre_matches

        for src, dst in remain_pre_matches:
            if src in src_nodes and dst in dst_nodes:
                cur_matches.append((src, dst))
                src_nodes.remove(src)
                dst_nodes.remove(dst)

        for src in src_nodes:
            find = False
            for dst in dst_nodes:
                if src + base_len != dst:
                    find = True
                    cur_matches.append((src, dst))
                    dst_nodes.remove(dst)
                    break
            if not find:
                dst = dst_nodes[0]
                src1, dst1 = cur_matches.pop()
                cur_matches.append((src1, dst))
                cur_matches.append((src, dst1))
        cur_matches.sort()
